﻿//152. 乘积最大子数组
//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组
//（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//测试用例的答案是一个 32 - 位 整数。

class Solution {
public:
    int maxProduct(vector<int>& nums)
    {
        int n = nums.size();
        vector<int> max_arr(n);
        vector<int> min_arr(n);
        max_arr[0] = min_arr[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            max_arr[i] = max(max_arr[i - 1] * nums[i], max(nums[i], min_arr[i - 1] * nums[i]));
            min_arr[i] = min(max_arr[i - 1] * nums[i], min(nums[i], min_arr[i - 1] * nums[i]));
        }
        return *max_element(max_arr.begin(), max_arr.end());
    }
};